﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Infrastructure.Commons.Sorting_Algorithm
{
    public class Sorting_Methods
    {
        #region 选择排序
        public void SelectSort(IList<int> data)
        {
            for (int i = 0; i < data.Count - 1; i++)
            {
                int min = i;
                int temp = data[i];
                for (int j = i + 1; j < data.Count; j++)
                {
                    if (data[j] < temp)
                    {
                        min = j;
                        temp = data[j];
                    }
                }
                if (min != i)
                {
                    Swap(data, min, i);
                }
            }

            Console.WriteLine("Start");
            StringBuilder stringBuilder = new StringBuilder();
            foreach (var data_Item in data)
            {
                stringBuilder.Append(data_Item.ToString() + " ");
            }
            Console.WriteLine(stringBuilder + "\r\n");
        }

        private void Swap(IList<int> data, int min, int i)
        {
            int temp = data[min];
            data[min] = data[i];
            data[i] = temp;
        }
        #endregion

        #region 快速排序
        public void QuickSortStrict(IList<int> data, int low, int high)
        {
            if (low >= high)
            {
                return;
            }

            int temp = data[low];
            int i = low + 1, j = high;
            while (true)
            {
                while (data[j] > temp)
                {
                    j--;
                }
                while (data[i] < temp && i < j)
                {
                    i++;
                }
                if (i >= j)
                {
                    break;
                }
                Swap(data, i, j);
                i++;
                j--;
            }
            if (j != low)
            {
                Swap(data, low, j);
            }
            QuickSortStrict(data, j + 1, high);
            QuickSortStrict(data, low, j - 1);
        }
        #endregion

        #region 快速排序（维基版）
        public void QuickSortRelax(IList<int> data, int low, int high)
        {
            if (low >= high) return;
            int temp = data[(low + high) / 2];
            int i = low - 1, j = high + 1;
            while (true)
            {
                while (data[++i] < temp) ;
                while (data[--j] > temp) ;
                if (i >= j) break;
                Swap(data, i, j);
            }
            QuickSortRelax(data, j + 1, high);
            QuickSortRelax(data, low, i - 1);
        }
        #endregion
    }
}
